package binarytree;

import java.util.*;

public class BinaryTree {

    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }


    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode a = new TreeNode('0');
        TreeNode b = new TreeNode('2');
        TreeNode c = new TreeNode('2');
        TreeNode d = new TreeNode('3');
        TreeNode e = new TreeNode('4');
        TreeNode f = new TreeNode('4');
        TreeNode g = new TreeNode('3');
//        TreeNode g = new TreeNode('g');
//        TreeNode h = new TreeNode('h');
//        TreeNode i = new TreeNode('i');
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        return a;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public static int nodeSize;

    /**
     * 获取树中节点的个数：遍历思路
     */
    void size(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            size(root.left);
        }
        if (root.left != null) {
            size(root.right);
        }
        nodeSize += 1;
    }

    /**
     * 获取节点的个数：子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return size2(root.right) + size2(root.left) + 1;
    }


    /*
     获取叶子节点的个数：遍历思路
     */
    public static int leafSize = 0;

    void getLeafNodeCount1(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafSize += 1;
        }
        if (root.left != null) {
            getLeafNodeCount1(root.left);
        }
        if (root.left != null) {
            getLeafNodeCount1(root.right);
        }
    }

    /*
     获取叶子节点的个数：子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

    /*
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k - 1) +  + getKLevelNodeCount(root.right,k - 1);
    }

    /*
     获取二叉树的高度
     时间复杂度：O(N)
     */
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return  1;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return 1 + Math.max(leftHeight, rightHeight);
    }


    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode left = find(root.left,val);
        if (left != null) {
            return left;
        }
        TreeNode right = find(root.right,val);
        if (right != null) {
            return right;
        }
        return null;
    }

    //层序遍历
    void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.offer(root);
        TreeNode treeNode;
        while(!treeNodes.isEmpty()) {
            treeNode = treeNodes.poll();
            System.out.print(treeNode.val + " ");
            if (treeNode.left != null) {
                treeNodes.offer(treeNode.left);
            }
            if (treeNode.right != null) {
                treeNodes.offer(treeNode.right);
            }
        }
    }


    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> treeNodes = new LinkedList<>();
        boolean isFirstStage = true;
        treeNodes.offer(root);
        while (!treeNodes.isEmpty()) {
            TreeNode treeNode = treeNodes.poll();
            if (isFirstStage) {
                if (treeNode.left == null&&treeNode.right == null) {
                    isFirstStage = false;
                }else if (treeNode.left != null&&treeNode.right == null) {
                    treeNodes.offer(treeNode.left);
                    isFirstStage = false;
                }else if (treeNode.left == null&&treeNode.right !=null){
                    return false;
                }else {
                    treeNodes.offer(treeNode.left);
                    treeNodes.offer(treeNode.right);
                }
            }else if (treeNode.left != null||treeNode.right != null) {
                return false;
            }
        }
        return true;
    }

    //二叉树前序非递归遍历
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> tree = new Stack<>();
        TreeNode cur = null;
        tree.push(root);
        while (!tree.empty()) {
            cur = tree.pop();
            list.add(cur.val);
            if (cur.right != null) {
                tree.push(cur.right);
            }
            if (cur.left != null) {
                tree.push(cur.left);
            }
        }
        return list;
    }

    //二叉树中序非递归遍历
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list= new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> tree = new Stack<>();
        TreeNode cur = root;
        while (true) {
            while (cur != null) {
                tree.push(cur);
                cur = cur.left;
            }
            if (tree.isEmpty()) {
                break;
            }
            TreeNode top = tree.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }

    //二叉树的后序非递归遍历
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list= new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> tree = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (true) {
            while (cur != null) {
                tree.push(cur);
                cur = cur.left;
            }
            if (tree.isEmpty()) {
                break;
            }
            TreeNode top = tree.peek();
            if(top.right == null || prev == top.right) {
                list.add(top.val);
                tree.pop();
                prev = top;
            }else if (top.right != null) {
                cur = top.right;
            }
        }
        return list;
    }

    //根据二叉树创建字符串
    private StringBuilder result = new StringBuilder();
    public String tree2str(TreeNode root) {
        tree(root);
        result.deleteCharAt(0);
        result.deleteCharAt(result.length() - 1);
        return result.toString();
    }

    public void tree(TreeNode root) {
        if (root != null) {
            result.append("(");
            result.append(root.val);
            if (root.left == null && root.right != null) {
                result.append("()");
            }
            tree(root.left);
            tree(root.right);
            result.append(")");
        }
    }

    //检查两棵树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (q == null && p == null) {
            return true;
        }
        if (q != null && p == null) {
            return false;
        }
        if (q == null && p != null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root.left == null && root.right == null) {
            return true;
        }
        if (root.left != null && root.right != null) {
            return isSymmetric2(root.left,root.right);
        }
        return false;
    }
    public boolean isSymmetric2(TreeNode p,TreeNode q) {
        if (q == null && p == null) {
            return true;
        }
        if (q != null && p == null) {
            return false;
        }
        if (q == null && p != null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        boolean out = isSymmetric2(p.left,q.right);
        boolean in = isSymmetric2(p.right,q.left);
        return out && in;
    }

    //另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) {
            return true;
        }
        if(root==null){
            return false;
        }
        return isSameTree(root,subRoot)||isSubtree(root.right,subRoot) || isSubtree(root.left,subRoot);
    }

    //判断一棵二叉树是否为平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int left = high(root.left);
        int right = high(root.right);
        if (left - right >= 1 || left - right <=-1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int high(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = high(root.left);
        int right = high(root.right);
        return 1 + (left > right ? left : right);
    }

    //二叉树的构建及遍历
    /*
    https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
     */
    static int index = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            TreeNode root = tree(a);
            out(root);
            System.out.println();
        }
    }
    public static TreeNode tree(String s) {
        char a = s.charAt(index);
        TreeNode root = null;
        if (a != '#') {
            root = new TreeNode(a);
        }else {
            return null;
        }
        index++;
        root.left = tree(s);
        index++;                       //!!!!!!!!!
        root.right = tree(s);
        return root;
    }
    public static void out(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> tree = new Stack<>();
        TreeNode cur = root;
        while (true) {
            while (cur != null) {
                tree.push(cur);
                cur = cur.left;
            }
            if (tree.isEmpty()) {
                break;
            }
            cur = tree.pop();
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }

    //二叉树的分层遍历
    /*
    https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/681516307/
     */
    public List<List<Character>> levelOrder1(TreeNode root) {
        List<List<Character>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        levelRow(root,0,list);
        return list;
    }
    public void levelRow(TreeNode root,int level,List<List<Character>> list) {
        if (root == null) {
            return;
        }
        if (list.size() == level) {
            list.add(new ArrayList<>());
        }
        List<Character> curRow = list.get(level);
        curRow.add(root.val);
        levelRow(root.left,level + 1,list);
        levelRow(root.right,level + 1,list);
    }

    //两个节点的最近公共祖先
    public TreeNode lca = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        lca = null;
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        include(root,p,q);
        return lca;
    }
    public int include(TreeNode root,TreeNode p,TreeNode q) {
        if (root == null) {
            return 0;
        }
        int curmid = root == p || root == q ? 1 : 0;
        int left = include(root.left,p,q);
        int right = include(root.right,p,q);
        if (curmid + left + right == 2) {
            lca = root;
        }
        return curmid + left + right > 0 ? 1 : 0;
    }
}
